{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1, 2, 0, 1, 2, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "# 计算字符串的前缀数组\n",
    "def prefix_table(string):\n",
    "    table = [None] * len(string)\n",
    "    table[0] = 0\n",
    "    # i从第二个开始比较，因为第一个前缀已经确定为0, j表示当前子串最后一个字符\n",
    "    j, i = 0, 1\n",
    "    while i < len(table):\n",
    "        # 如果相等就记录\n",
    "        if string[i] == string[j]:\n",
    "            j += 1\n",
    "            table[i] = j\n",
    "            i += 1\n",
    "        else:\n",
    "            if j > 0:\n",
    "                j = table[j - 1]\n",
    "            else:\n",
    "                table[i] = j\n",
    "                i += 1\n",
    "    return table\n",
    "    pass\n",
    "table = prefix_table(\"ababcabaa\")\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, 0, 0, 1, 2, 0, 1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "# 前缀表移位\n",
    "def move_prefix_table(table):\n",
    "    if not table:\n",
    "        return\n",
    "    for i in range(len(table)-1, 0, -1):\n",
    "        table[i] = table[i-1]\n",
    "    table[0] = -1\n",
    "    return table\n",
    "table = move_prefix_table(table)\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "text:\n",
      "asdasdjdhfdjkfjdkfasdljhgdshfgklsadjaskdhgfdkfjdsflkjfdjgkhdfjkghaslfdgjdfghkjfghjkdfgksgkhdsjkghsfjjgslkdjfkl\n",
      "\n",
      "pattern:\n",
      "jds\n",
      "\n",
      "\n",
      "found pattern at 46\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# kmp字符串匹配算法实现\n",
    "def kmp(text, pattern):\n",
    "    # 计算前缀表\n",
    "    prefix = move_prefix_table(prefix_table(pattern))\n",
    "    # text[i] - 长度m\n",
    "    # pattern[j] - 长度n\n",
    "    i, j, m, n = 0, 0, len(text), len(pattern)\n",
    "    if m < n:\n",
    "        print(\"not match any pattern\")\n",
    "    while i < m:\n",
    "        # 找到匹配\n",
    "        if j == n - 1 and text[i] == pattern[j]:\n",
    "            print(\"found pattern at %d\\n\"%(i-j))\n",
    "            # 往前寻找下一次匹配\n",
    "            j = prefix[j]\n",
    "        if text[i] == pattern[j]:\n",
    "            i += 1\n",
    "            j += 1\n",
    "        else:\n",
    "            # 待匹配字符串回溯到对应的前缀表位置\n",
    "            j = prefix[j]\n",
    "            # 遇到-1，待匹配和匹配字符串都右移一位\n",
    "            if j == -1:\n",
    "                i += 1\n",
    "                j += 1\n",
    "    pass\n",
    "\n",
    "text = \"\"\"asdasdjdhfdjkfjdkfasdljhgdshfgklsadjaskdhgfdkfjdsflkjfdjgkhdfjkghaslfdgjdfghkjfghjkdfgksgkhdsjkghsfjjgslkdjfkl\"\"\"\n",
    "print(\"\\ntext:\\n\"+text)\n",
    "pattern = 'jds'\n",
    "print(\"\\npattern:\\n\"+ pattern)\n",
    "print('\\n')\n",
    "kmp(text,pattern)\n",
    "                "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:zhong]",
   "language": "python",
   "name": "conda-env-zhong-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
